#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

struct DLinkNode{
    int val;
    int key;
    DLinkNode* prev;
    DLinkNode* next;
    DLinkNode(int x, int y): key(x), val(y), prev(nullptr), next(nullptr){}
    DLinkNode(): key(0), val(0), prev(nullptr), next(nullptr){}
};


class LRUCache{
    public:
    LRUCache(int x){
        size = 0;
        capacity = x;
        head = new DLinkNode();
        tail = new DLinkNode();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key){
        if(!cache.count(key)){
            return -1;
        }
        DLinkNode* node = cache[key];
        moveToHead(node);
        return node->val;
    }

    void put(int key, int value){
        if(!cache.count(key)){
            DLinkNode* node = new DLinkNode(key, value);
            cache[key] = node;
            addToHead(node);
            size++;
            if(size > capacity){
                DLinkNode* remove = removeTail();
                cache.erase(remove->key);
                delete remove;
                size--;
            }
        }else{
            DLinkNode* node = new DLinkNode(key, value);
            cache[key] = node;
            moveToHead(node);
        }
    }


    void addToHead(DLinkNode* node){
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void removeNode(DLinkNode* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkNode* node){
        removeNode(node);
        addToHead(node);
    }

    DLinkNode* removeTail(){
        DLinkNode* node = tail->prev;
        removeNode(node);
        return node;
    }

    private:
    unordered_map<int, DLinkNode*> cache;
    DLinkNode* head;
    DLinkNode* tail;
    int size;
    int capacity;
};

void test(){
    LRUCache* lRUCache = new LRUCache(2);
    lRUCache->put(1, 1);
    lRUCache->put(2, 2);
    cout << lRUCache->get(1) << endl;
    lRUCache->put(3, 3);
    cout << lRUCache->get(2) << endl;
    lRUCache->put(4, 4);
    cout << lRUCache->get(1) << endl;
    cout << lRUCache->get(3) << endl;
    cout << lRUCache->get(4) << endl;
}

int main(void){
    test();

    return 0;
}